#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <climits>

using namespace std;

// Generate a random page reference string
vector<int> generateReferenceString(int length = 20, int pageRange = 10) {
    vector<int> refStr;
    for (int i = 0; i < length; ++i) {
        refStr.push_back(rand() % pageRange);
    }
    return refStr;
}

// FIFO Page Replacement Algorithm
int fifo(const vector<int>& pages, int framesCount) {
    unordered_set<int> frames;
    queue<int> queue; // Records the order of page insertion
    int faults = 0;

    for (int page : pages) {
        if (frames.find(page) == frames.end()) {
            faults++;
            if (static_cast<int>(frames.size()) < framesCount) {
                frames.insert(page);
                queue.push(page);
            } else {
                int oldest = queue.front();
                queue.pop();
                frames.erase(oldest);
                frames.insert(page);
                queue.push(page);
            }
        }
    }
    return faults;
}

// LRU Page Replacement Algorithm
int lru(const vector<int>& pages, int framesCount) {
    unordered_map<int, int> lastUsed; // page -> last access time
    unordered_set<int> frames;
    int faults = 0;
    int time = 0;

    for (int page : pages) {
        time++;
        if (frames.find(page) != frames.end()) {
            lastUsed[page] = time; // Update access time
        } else {
            faults++;
            if (static_cast<int>(frames.size()) < framesCount) {
                frames.insert(page);
                lastUsed[page] = time;
            } else {
                // Find the least recently used page (smallest lastUsed time)
                int lruPage = -1;
                int earliestTime = INT_MAX;
                for (int f : frames) {
                    if (lastUsed[f] < earliestTime) {
                        earliestTime = lastUsed[f];
                        lruPage = f;
                    }
                }
                frames.erase(lruPage);
                lastUsed.erase(lruPage);
                frames.insert(page);
                lastUsed[page] = time;
            }
        }
    }
    return faults;
}

// OPT (Optimal) Page Replacement Algorithm
int optimal(const vector<int>& pages, int framesCount) {
    unordered_set<int> frames;
    int faults = 0;
    int n = pages.size();

    for (int i = 0; i < n; ++i) {
        int page = pages[i];
        if (frames.find(page) == frames.end()) {
            faults++;
            if (static_cast<int>(frames.size()) < framesCount) {
                frames.insert(page);
            } else {
                // Find the page in frames that is used furthest in the future (or never again)
                int farthest = -1;
                int toEvict = -1;
                for (int f : frames) {
                    int nextUse = INT_MAX;
                    // Look ahead to find next use of page f
                    for (int j = i + 1; j < n; ++j) {
                        if (pages[j] == f) {
                            nextUse = j;
                            break;
                        }
                    }
                    if (nextUse > farthest) {
                        farthest = nextUse;
                        toEvict = f;
                    }
                }
                frames.erase(toEvict);
                frames.insert(page);
            }
        }
    }
    return faults;
}

int main() {
    const int REF_LENGTH = 20;
    const int PAGE_RANGE = 10; // Pages from 0 to 9
    const int MAX_FRAMES = 7;

    // Seed the random number generator
    srand(static_cast<unsigned int>(time(0)));

    vector<int> referenceString = generateReferenceString(REF_LENGTH, PAGE_RANGE);

    cout << "Page Reference String: ";
    for (int p : referenceString) {
        cout << p << " ";
    }
    cout << "\n";
    cout << "============================================================\n";
    cout << "Frames  FIFO    LRU     OPT\n";
    cout << "-----------------------------------\n";

    for (int frames = 1; frames <= MAX_FRAMES; ++frames) {
        int fifoFaults = fifo(referenceString, frames);
        int lruFaults = lru(referenceString, frames);
        int optFaults = optimal(referenceString, frames);

        cout << frames << "       " 
             << fifoFaults << "       " 
             << lruFaults << "       " 
             << optFaults << "\n";
    }

    return 0;
}